package com.yangzhe.algorithm.c027;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;





/**
 * 类名修改成Solution提交可通过
 * 合并K个有序链表
 * 测试链接：https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
 */
public class Code01_MergeKSortedLists_Acm {

    /**
     * 这段需要注释后再提交
     */
    public class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }

    private static PriorityQueue<ListNode> smallHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 定义一个小根堆做缓存，小根堆头节点就是堆中最小的数
     * 每次将所有链表的下一个节点放入小根堆，再弹出，则相当于每次比较出多个链表最小的那个节点
     * 弹出的节点拼接到结果链表中即可
     *
     * 因为小根堆最多会有K个数，所以每次调整小根堆实际上就是 O(logK)的复杂度，最终
     * 时间复杂度O(N * logK)  额外空间复杂度 O(K)
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        ListNode head = null;
        // 1. 把所有头节点放到小根堆
        for (ListNode node : lists) {
            if (node != null) {
                smallHeap.add(node);
            }
        }

        // 2. 如果头节点都为空，则直接返回空
        if (smallHeap.isEmpty()) {
            return head;
        }

        // 3. 弹出一个节点，做总头部，总头部指针不变
        head = smallHeap.poll();

        // 4. 定义当前节点用于遍历
        ListNode cur = head;
        if (cur.next != null) {
            smallHeap.add(cur.next);
        }

        // 5. 小根堆不为空，则继续弹出一个节点，做当前节点的下一个节点
        while(!smallHeap.isEmpty()) {
            ListNode node = smallHeap.poll();
            cur.next = node;
            cur = node;
            if (node.next != null) {
                smallHeap.add(node.next);
            }

        }
        return head;
    }

}